YES 48.722 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:



HASKELL
  ↳ LR

mainModule Main
  ((lines :: [Char ->  [[Char]]) :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Lambda Reductions:
The following Lambda expression
\(l,_)→l

is transformed to
l0 (l,_) = l

The following Lambda expression
\(_,s')→s'

is transformed to
s'0 (_,s') = s'

The following Lambda expression
\(_,zs)→zs

is transformed to
zs0 (_,zs) = zs

The following Lambda expression
\(ys,_)→ys

is transformed to
ys0 (ys,_) = ys



↳ HASKELL
  ↳ LR
HASKELL
      ↳ CR

mainModule Main
  ((lines :: [Char ->  [[Char]]) :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Case Reductions:
The following Case expression
case s' of
 [] → []
 : s'' → lines s''

is transformed to
lines0 [] = []
lines0 (_ : s'') = lines s''



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
HASKELL
          ↳ BR

mainModule Main
  ((lines :: [Char ->  [[Char]]) :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Replaced joker patterns by fresh variables and removed binding patterns.
Binding Reductions:
The bind variable of the following binding Pattern
xs@(vz : wu)

is replaced by the following term
vz : wu



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
HASKELL
              ↳ COR

mainModule Main
  ((lines :: [Char ->  [[Char]]) :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Cond Reductions:
The following Function with conditions
undefined 
 | False
 = undefined

is transformed to
undefined  = undefined1

undefined0 True = undefined

undefined1  = undefined0 False

The following Function with conditions
span p [] = ([],[])
span p (vz : wu)
 | p vz
 = (vz : ys,zs)
 | otherwise
 = ([],vz : wu)
where 
vu43  = span p wu
ys  = ys0 vu43
ys0 (ys,wv) = ys
zs  = zs0 vu43
zs0 (ww,zs) = zs

is transformed to
span p [] = span3 p []
span p (vz : wu) = span2 p (vz : wu)

span2 p (vz : wu) = 
span1 p vz wu (p vz)
where 
span0 p vz wu True = ([],vz : wu)
span1 p vz wu True = (vz : ys,zs)
span1 p vz wu False = span0 p vz wu otherwise
vu43  = span p wu
ys  = ys0 vu43
ys0 (ys,wv) = ys
zs  = zs0 vu43
zs0 (ww,zs) = zs

span3 p [] = ([],[])
span3 xu xv = span2 xu xv



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
HASKELL
                  ↳ LetRed

mainModule Main
  ((lines :: [Char ->  [[Char]]) :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Let/Where Reductions:
The bindings of the following Let/Where expression
let 
l  = l0 vu44
l0 (l,vv) = l
lines0 [] = []
lines0 (vw : s'') = lines s''
s'  = s'0 vu44
s'0 (vx,s') = s'
vu44  = break ('\10' ==s
in l : lines0 s'

are unpacked to the following functions on top level
linesL xw = linesL0 xw (linesVu44 xw)

linesS'0 xw (vx,s') = s'

linesVu44 xw = break ('\10' ==xw

linesL0 xw (l,vv) = l

linesS' xw = linesS'0 xw (linesVu44 xw)

linesLines0 xw [] = []
linesLines0 xw (vw : s'') = lines s''

The bindings of the following Let/Where expression
span1 p vz wu (p vz)
where 
span0 p vz wu True = ([],vz : wu)
span1 p vz wu True = (vz : ys,zs)
span1 p vz wu False = span0 p vz wu otherwise
vu43  = span p wu
ys  = ys0 vu43
ys0 (ys,wv) = ys
zs  = zs0 vu43
zs0 (ww,zs) = zs

are unpacked to the following functions on top level
span2Span1 xx xy p vz wu True = (vz : span2Ys xx xy,span2Zs xx xy)
span2Span1 xx xy p vz wu False = span2Span0 xx xy p vz wu otherwise

span2Span0 xx xy p vz wu True = ([],vz : wu)

span2Ys0 xx xy (ys,wv) = ys

span2Vu43 xx xy = span xx xy

span2Ys xx xy = span2Ys0 xx xy (span2Vu43 xx xy)

span2Zs0 xx xy (ww,zs) = zs

span2Zs xx xy = span2Zs0 xx xy (span2Vu43 xx xy)



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
HASKELL
                      ↳ NumRed

mainModule Main
  ((lines :: [Char ->  [[Char]]) :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.

↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
HASKELL
                          ↳ Narrow

mainModule Main
  (lines :: [Char ->  [[Char]])

module Main where
  import qualified Prelude



Haskell To QDPs


↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
                        ↳ HASKELL
                          ↳ Narrow
                            ↳ AND
QDP
                                ↳ QDPSizeChangeProof
                              ↳ QDP
                              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_span2Ys00(xz282, xz283, xz284) → new_span2Ys(xz282, xz284)
new_span2Ys0(xz282, xz283, xz284, Succ(xz2850), Zero) → new_span2Ys(xz282, xz284)
new_span2Ys0(xz282, xz283, xz284, Succ(xz2850), Succ(xz2860)) → new_span2Ys0(xz282, xz283, xz284, xz2850, xz2860)
new_span2Ys0(xz282, xz283, xz284, Zero, Succ(xz2860)) → new_span2Ys00(xz282, xz283, xz284)
new_span2Ys(xz7, :(Char(Succ(xz6000)), xz61)) → new_span2Ys0(xz7, xz6000, xz61, xz7, xz6000)
new_span2Ys(xz7, :(Char(Zero), xz61)) → new_span2Ys(xz7, xz61)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
                        ↳ HASKELL
                          ↳ Narrow
                            ↳ AND
                              ↳ QDP
QDP
                                ↳ QDPSizeChangeProof
                              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_linesL0(xz111, xz112, xz113, Succ(xz1140), Succ(xz1150)) → new_linesL0(xz111, xz112, xz113, xz1140, xz1150)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ CR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
                        ↳ HASKELL
                          ↳ Narrow
                            ↳ AND
                              ↳ QDP
                              ↳ QDP
QDP
                                ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

new_linesLines0(Char(Zero), :(xz100, xz101), xz11) → new_linesLines01(:(xz100, xz101), xz11, xz100, xz101)
new_linesLines08(xz978, xz979, xz980, xz981, xz982) → new_linesLines07(xz978, xz979, xz980, xz981, xz982, new_span2Ys1(xz980, xz982))
new_linesLines013(xz887, xz888, xz889, xz890) → new_linesLines012(xz887, xz888, xz889, xz890, new_span2Ys1(xz888, xz890))
new_linesLines07(xz978, xz979, xz980, xz981, xz982, xz985) → new_linesLines09(xz978, xz979, xz980, xz982)
new_linesLines00(xz119, xz120, xz121, Succ(xz1220), Succ(xz1230)) → new_linesLines00(xz119, xz120, xz121, xz1220, xz1230)
new_linesLines01(xz797, xz798, Char(Succ(xz79900)), xz800) → new_linesLines010(xz797, xz798, xz79900, xz800, xz798, xz79900)
new_lines(:(xz30, xz31)) → new_linesLines0(xz30, xz31, Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Zero))))))))))
new_linesLines012(xz887, xz888, xz889, xz890, xz905) → new_linesLines014(xz887, xz888, xz890)
new_linesLines011(xz797, xz798, :(xz8000, xz8001), xz815) → new_linesLines01(xz797, xz798, xz8000, xz8001)
new_linesLines010(xz887, xz888, xz889, xz890, Succ(xz8910), Succ(xz8920)) → new_linesLines010(xz887, xz888, xz889, xz890, xz8910, xz8920)
new_linesLines010(xz887, xz888, xz889, xz890, Zero, Succ(xz8920)) → new_linesLines013(xz887, xz888, xz889, xz890)
new_linesLines04(xz940, xz941, xz942, Char(Zero), xz944) → new_linesLines06(xz940, xz941, xz942, xz944, new_span2Ys1(xz942, xz944))
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Succ(xz9830), Zero) → new_linesLines07(xz978, xz979, xz980, xz981, xz982, new_span2Ys1(xz980, xz982))
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Zero, Zero) → new_lines(xz982)
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Succ(xz9830), Succ(xz9840)) → new_linesLines05(xz978, xz979, xz980, xz981, xz982, xz9830, xz9840)
new_linesLines02(xz119, :(xz1200, xz1201), xz127, xz121) → new_linesLines04(xz119, :(xz1200, xz1201), xz121, xz1200, xz1201)
new_linesLines01(xz797, xz798, Char(Zero), xz800) → new_linesLines011(xz797, xz798, xz800, new_span2Ys1(xz798, xz800))
new_linesLines03(xz119, xz120, xz121) → new_linesLines02(xz119, xz120, new_span2Ys1(xz121, xz120), xz121)
new_linesLines0(Char(Succ(xz900)), xz10, xz11) → new_linesLines00(xz900, xz10, xz11, xz11, xz900)
new_linesLines04(xz940, xz941, xz942, Char(Succ(xz94300)), xz944) → new_linesLines05(xz940, xz941, xz942, xz94300, xz944, xz942, xz94300)
new_linesLines09(xz940, xz941, xz942, :(xz9440, xz9441)) → new_linesLines04(xz940, xz941, xz942, xz9440, xz9441)
new_linesLines00(xz119, xz120, xz121, Zero, Zero) → new_lines(xz120)
new_linesLines010(xz887, xz888, xz889, xz890, Succ(xz8910), Zero) → new_linesLines012(xz887, xz888, xz889, xz890, new_span2Ys1(xz888, xz890))
new_linesLines014(xz797, xz798, :(xz8000, xz8001)) → new_linesLines01(xz797, xz798, xz8000, xz8001)
new_linesLines00(xz119, xz120, xz121, Zero, Succ(xz1230)) → new_linesLines03(xz119, xz120, xz121)
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Zero, Succ(xz9840)) → new_linesLines08(xz978, xz979, xz980, xz981, xz982)
new_linesLines06(xz940, xz941, xz942, :(xz9440, xz9441), xz945) → new_linesLines04(xz940, xz941, xz942, xz9440, xz9441)
new_linesLines00(xz119, xz120, xz121, Succ(xz1220), Zero) → new_linesLines02(xz119, xz120, new_span2Ys1(xz121, xz120), xz121)
new_linesLines010(xz887, xz888, xz889, xz890, Zero, Zero) → new_lines(xz890)

The TRS R consists of the following rules:

new_span2Ys1(xz7, :(Char(Succ(xz6000)), xz61)) → new_span2Ys03(xz7, xz6000, xz61, xz7, xz6000)
new_span2Ys03(xz282, xz283, xz284, Succ(xz2850), Zero) → new_span2Ys01(xz282, xz283, xz284)
new_span2Ys03(xz282, xz283, xz284, Zero, Succ(xz2860)) → new_span2Ys01(xz282, xz283, xz284)
new_span2Ys03(xz282, xz283, xz284, Succ(xz2850), Succ(xz2860)) → new_span2Ys03(xz282, xz283, xz284, xz2850, xz2860)
new_span2Ys03(xz282, xz283, xz284, Zero, Zero) → []
new_span2Ys02(xz282, xz283, xz284, xz298) → :(Char(Succ(xz283)), xz298)
new_span2Ys1(xz7, :(Char(Zero), xz61)) → new_span2Ys04(xz7, xz61, new_span2Ys1(xz7, xz61))
new_span2Ys04(xz7, xz61, xz46) → :(Char(Zero), xz46)
new_span2Ys01(xz282, xz283, xz284) → new_span2Ys02(xz282, xz283, xz284, new_span2Ys1(xz282, xz284))
new_span2Ys1(xz7, []) → []

The set Q consists of the following terms:

new_span2Ys01(x0, x1, x2)
new_span2Ys03(x0, x1, x2, Zero, Zero)
new_span2Ys1(x0, :(Char(Succ(x1)), x2))
new_span2Ys02(x0, x1, x2, x3)
new_span2Ys03(x0, x1, x2, Succ(x3), Succ(x4))
new_span2Ys1(x0, [])
new_span2Ys03(x0, x1, x2, Zero, Succ(x3))
new_span2Ys04(x0, x1, x2)
new_span2Ys03(x0, x1, x2, Succ(x3), Zero)
new_span2Ys1(x0, :(Char(Zero), x1))

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs: